package com.caochenlei.graph;

import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearch {
    private boolean[] marked;                       //索引代表顶点，值表示当前顶点是否已经被搜索
    private int count;                              //记录有多少个顶点与顶点s相通

    public BreadthFirstSearch(Graph G, int s) {     //构造广度优先搜索对象
        this.marked = new boolean[G.size()];        //初始化marked数组
        this.count = 0;                             //初始化跟顶点s相通的顶点的数量
        bfs(G, s);                                  //使用广度优先搜索找出G图中顶点s的所有相邻顶点
    }

    private void bfs(Graph G, int v) {              //使用广度优先搜索找出G图中顶点v的所有相通顶点
        Queue<Integer> queue = new LinkedList<>();  //用来存储待搜索邻接表的点
        marked[v] = true;                           //把顶点v标识为已搜索
        count++;                                    //顶点v和顶点v自己是相通的，所以加一
        queue.add(v);                               //让顶点v进入队列，待搜索
        while (!queue.isEmpty()) {                  //如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
            Integer wait = queue.poll();            //弹出一个待搜索的顶点
            for (Integer w : G.adj(wait)) {         //遍历wait顶点的邻接表
                if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                    marked[w] = true;               //把w顶点标识为已搜索
                    count++;                        //顶点v和顶点w自己是相通的，所以加一
                    queue.add(w);                   //让顶点w进入队列，待搜索
                }
            }
        }
    }

    //判断w顶点与顶点s是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }
}